// https://leetcode.cn/problems/add-binary/
// 转成十进制计算会越界，直接字符上二进制计算

class Solution {
public:
    string addBinary(string a, string b) {
        int carry = 0;
        int p1 = a.length() - 1;
        int p2 = b.length() - 1;
        string res = "";
        while (p1 >= 0 && p2 >= 0) {
            res.insert(res.begin(), '0' + ((a[p1] - '0') ^ (b[p2] - '0')) ^ carry);
            // carry = (a[p1] - '0') & (b[p2] - '0') & carry; 注意，三个不对了
            carry = ((a[p1] - '0') + (b[p2] - '0') + carry) / 2;
            p1--;
            p2--;
        }
        while (p1 >= 0) {
            res.insert(res.begin(), '0' + ((a[p1] - '0') ^ carry));
            carry = (a[p1] - '0') & carry;
            p1--;
        }
        while (p2 >= 0) {
            res.insert(res.begin(), '0' + ((b[p2] - '0') ^ carry));
            carry = (b[p2] - '0') & carry;
            p2--;
        }
        if (carry) res.insert(res.begin(), '0' + carry);
        return res;
    }
};